package cn.weihuachao;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class Solution {

    public void getMainPath(ArrayList<List<Integer>> graph) {

        // 获取简单路径，从每个点出发，把经历过的所有路径进行记录
        HashSet<String> easyPath = new HashSet<>();
        for (int i = 1; i < graph.size(); i++) {
            List<Integer> tmp = new LinkedList<>();
            tmp.add(i);
            easyPath(easyPath, graph, tmp, new HashSet<>(), i);
        }
        System.out.println("简单路径为: " + easyPath);

        // 找主路径
        // 先从入度为 0 的点开始找
        Set<String> ans = new HashSet<>();
        ArrayList<List<Integer>> intoTheDegree = new ArrayList<>(graph.size());
        for (int i = 0; i < 8; i++) {
            intoTheDegree.add(new LinkedList<>());
        }
        for (int i = 0; i < graph.size(); i++) {
            final int in = i;
            graph.get(in).forEach(v -> intoTheDegree.get(v).add(in));
        }
        for (int i = 1; i < intoTheDegree.size(); i++) {
            if (intoTheDegree.get(i).size() == 0) {
                List<Integer> tmp = new LinkedList<>();
                tmp.add(i);
                dfs(ans, graph, tmp, new HashSet<>(), i);
            }
        }

        // 找到环路径以及环上的点
        Set<Integer> cyclePoints = new HashSet<>();
        for (int i = 1; i < graph.size(); i++) {
            List<Integer> tmp = new LinkedList<>();
            tmp.add(i);
            getCycle(ans, graph, tmp, cyclePoints, new HashSet<>(), i);
        }

        // 从在环上的点开始补充主路径
        cyclePoints.forEach(point -> {
            List<Integer> in = intoTheDegree.get(point);
            for (Integer integer : in) {
                if (!cyclePoints.contains(integer)) {
                    return;
                }
            }
            List<Integer> tmp = new LinkedList<>();
            tmp.add(point);
            dfsCycle(ans, graph, tmp, new HashSet<>(), point);
        });
        System.out.println("主路径为: " + ans);
    }

    private void easyPath(Set<String> ans, ArrayList<List<Integer>> graph, List<Integer> tmpAns, Set<Integer> points, Integer curr) {
        if (points.contains(curr)) {
            if (tmpAns.get(0).equals(curr)) {
                ans.add(getResult(tmpAns));
            }
            return;
        }
        ans.add(getResult(tmpAns));
        points.add(curr);
        if (graph.get(curr) != null && graph.get(curr).size() > 0) {
            graph.get(curr).forEach(tmpPoint -> {
                tmpAns.add(tmpPoint);
                easyPath(ans, graph, tmpAns, points, tmpPoint);
                tmpAns.remove(tmpAns.size() - 1);
            });
        } else {
            ans.add(getResult(tmpAns));
        }
        points.remove(curr);
    }

    private void dfs(Set<String> ans, ArrayList<List<Integer>> graph, List<Integer> tmpAns, Set<Integer> points, Integer curr) {
        if (points.contains(curr)) {
            ans.add(getCycleResult(tmpAns));
            return;
        }
        points.add(curr);
        if (graph.get(curr) != null && graph.get(curr).size() > 0) {
            graph.get(curr).forEach(tmpPoint -> {
                tmpAns.add(tmpPoint);
                dfs(ans, graph, tmpAns, points, tmpPoint);
                tmpAns.remove(tmpAns.size() - 1);
            });
        } else {
            ans.add(getResult(tmpAns));
        }
        points.remove(curr);
    }

    private void dfsCycle(Set<String> ans, ArrayList<List<Integer>> graph, List<Integer> tmpAns, Set<Integer> points, Integer curr) {
        if (points.contains(curr)) {
            return;
        }
        points.add(curr);
        if (graph.get(curr) != null && graph.get(curr).size() > 0) {
            graph.get(curr).forEach(tmpPoint -> {
                tmpAns.add(tmpPoint);
                dfsCycle(ans, graph, tmpAns, points, tmpPoint);
                tmpAns.remove(tmpAns.size() - 1);
            });
        } else {
            ans.add(getResult(tmpAns));
        }
        points.remove(curr);
    }

    private String getResult(List<Integer> tmp) {
        StringBuilder ans = new StringBuilder();
        for (Integer integer : tmp) {
            ans.append(integer);
        }
        return ans.toString();
    }

    private String getCycleResult(List<Integer> tmp) {
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < tmp.size() - 1; i++) {
            ans.append(tmp.get(i));
        }
        return ans.toString();
    }

    private void getCycle(Set<String> ans, ArrayList<List<Integer>> graph, List<Integer> tmpAns, Set<Integer> cycle, Set<Integer> points,
                          Integer curr) {
        if (points.contains(curr)) {
            boolean need = false;
            StringBuilder sb = new StringBuilder();
            for (int num : tmpAns) {
                if (num == curr) {
                    need = true;
                }
                if (need) {
                    sb.append(num);
                    cycle.add(num);
                }
            }
            ans.add(sb.toString());
            return;
        }
        points.add(curr);
        if (graph.get(curr) != null && graph.get(curr).size() > 0) {
            graph.get(curr).forEach(tmpPoint -> {
                tmpAns.add(tmpPoint);
                getCycle(ans, graph, tmpAns, cycle, points, tmpPoint);
                tmpAns.remove(tmpAns.size() - 1);
            });
        }
        points.remove(curr);
    }

    public static void main(String[] args) {
        ArrayList<List<Integer>> graph = new ArrayList<>(8);
        for (int i = 0; i < 8; i++) {
            graph.add(new LinkedList<>());
        }
        graph.set(1, List.of(2, 3));
        graph.set(2, List.of(3));
        graph.set(3, List.of(4, 5));
        graph.set(4, List.of(7));
        graph.set(5, List.of(6, 7));
        graph.set(6, List.of(5));
        graph.set(7, List.of());

        Solution solution = new Solution();
        solution.getMainPath(graph);
    }
}
